package leetcode_901_1000;

import java.util.Arrays;

public class LeeCode_983 {
    public static void main(String[] args) {
        System.out.println(mincostTickets(new int[]{1, 4, 6, 7, 8, 20}, new int[]{2, 7, 15}));
    }
    private static int mincostTickets(int[] days, int[] costs) {
        Arrays.sort(days);
        int n = days.length;
        int[][] dp = new int[n][4];
        dp[0][0] = costs[0];
        dp[0][1] = costs[1];
        dp[0][2] = costs[2];
        dp[0][3] = Math.min(dp[0][0], Math.min(dp[0][1], dp[0][2]));
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i - 1][3] + costs[0];
            int goal = days[i] - 6;
            int index = search(days, goal);
            if (index == -1){
                dp[i][1] = costs[1];
            }else {
                dp[i][1] = costs[1] + dp[index][3];
            }
            goal = days[i] - 29;
            index = search(days, goal);
            if (index == -1){
                dp[i][2] = costs[2];
            }else {
                dp[i][2] = costs[2] + dp[index][3];
            }
            dp[i][3] = Math.min(dp[i][0], Math.min(dp[i][1], dp[i][2]));
        }
        return dp[n - 1][3];
    }
    private static int search(int[] days, int goal){
        int l = 0, r = days.length - 1;
        while (l < r){
            int m = (l + r + 1) >>> 1;
            if (days[m] >= goal){
                r = m - 1;
            }else {
                l = m;
            }
        }
        if (days[l] >= goal)
            return -1;
        return l;
    }
}
